package com.company.ljh.easy;
/**
 * 请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
 */

import com.company.ljh.utils.TreeNode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @description:
 * @projectName:leet_code
 * @see:com.company.ljh.easy
 * @author:ljh
 * @createTime:2022/6/7 15:15
 * @version:1.0
 */
public class 从上到下打印二叉树III {
    //双端队列
    public List<List<Integer>> levelOrder(TreeNode root) {

        List<List<Integer>> result = new ArrayList();
        if(root == null){
            return result;
        }
        int i =0;
        listTreeNode(root,i,result);
        return result;
    }
    private void listTreeNode(TreeNode root, int i, List<List<Integer>> result){
        Deque<Integer> list;
        if(result.size() < i+1){
            list = new LinkedList<Integer>();
            result.add((List)list);
        }else{
            list = (Deque)result.get(i);
        }
        if(i % 2 ==1)
            //反向存储
            list.offerFirst(root.val);
        else
            list.offer(root.val);
        if(root.left != null){
            listTreeNode(root.left,i+1,result);
        }
        if(root.right != null){
            listTreeNode(root.right,i+1,result);
        }
    }
}
